home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 November / EnigmA AMIGA RUN 02 (1995)(G.R. Edizioni)(IT)[!][issue 1995-11][Skylink CD].iso / earcd / program / gcc / ixemul-4.lha / ixemul-41.4 / network / hash.h < prev    next >
C/C++ Source or Header  |  1995-05-18  |  10KB  |  281 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  *
  36.  *    @(#)hash.h    5.4 (Berkeley) 3/12/91
  37.  */
  38.  
  39. /* Operations */
  40. typedef enum { HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, 
  41.         HASH_FIRST, HASH_NEXT } ACTION;
  42.  
  43. /* Buffer Management structures */
  44. typedef struct _bufhead BUFHEAD;
  45.  
  46. struct _bufhead {
  47.     BUFHEAD    *prev;        /* LRU links */
  48.     BUFHEAD    *next;        /* LRU links */
  49.     BUFHEAD    *ovfl;        /* Overflow page buffer header */
  50.     u_int     addr;        /* Address of this page */
  51.     char    *page;        /* Actual page data */
  52.     char    flags;    
  53. #define    BUF_MOD        0x0001
  54. #define BUF_DISK    0x0002
  55. #define    BUF_BUCKET    0x0004
  56. #define    BUF_PIN        0x0008
  57. };
  58.  
  59.  
  60. #define IS_BUCKET(X)    (X & BUF_BUCKET)
  61.  
  62. typedef BUFHEAD    **SEGMENT;
  63.  
  64. /* Hash Table Information */
  65. typedef struct hashhdr {    /* Disk resident portion */
  66.     int magic;    /* Magic NO for hash tables */
  67.     int version;    /* Version ID */
  68.     long lorder;    /* Byte Order */
  69.     int bsize;    /* Bucket/Page Size */
  70.     int bshift;    /* Bucket shift */
  71.     int dsize;    /* Directory Size */
  72.     int ssize;    /* Segment Size */
  73.     int sshift;    /* Segment shift */
  74.     int max_bucket;    /* ID of Maximum bucket in use */
  75.     int high_mask;    /* Mask to modulo into entire table */
  76.     int low_mask;    /* Mask to modulo into lower half of table */
  77.     int ffactor;    /* Fill factor */
  78.     int nkeys;    /* Number of keys in hash table */
  79.     int hdrpages;    /* Size of table header */
  80.     int h_charkey;    /* value of hash(CHARKEY) */
  81. # define NCACHED        32    /* number of bit maps and spare points*/
  82.     int spares[NCACHED];    /* spare pages for overflow */
  83.     u_short bitmaps[NCACHED];    /* address of overflow page bitmaps */
  84. } HASHHDR;
  85.  
  86. typedef struct htab {    /* Memory resident data structure */
  87.     HASHHDR hdr;    /* Header */
  88.     int nsegs;    /* Number of allocated segments */
  89.     int exsegs;    /* Number of extra allocated segments */
  90.     int (*hash)();    /* Hash Function */
  91.     int flags;    /* Flag values */
  92.     int fp;        /* File pointer */
  93.     char *tmp_buf;    /* Temporary Buffer for BIG data */
  94.     char *tmp_key;    /* Temporary Buffer for BIG keys */
  95.     BUFHEAD *cpage;    /* Current page */
  96.     int cbucket;    /* Current bucket */
  97.     int cndx;      /* Index of next item on cpage */
  98.     int errno;    /* Error Number -- for DBM compatability */
  99.     int new_file;    /* Indicates whether fd is backing store or no */
  100.     int save_file;    /* Indicates whether we need to flush file at exit */
  101.     u_long *mapp[NCACHED];    /* Pointers to page maps */
  102.     int nmaps;    /* Initial number of bitmaps */
  103.     int nbufs;    /* Number of buffers left to allocate */
  104.     BUFHEAD    bufhead; /* Header of buffer lru list */
  105.     SEGMENT     *dir;    /* Hash Bucket directory */
  106. } HTAB;
  107.  
  108.  
  109. /*
  110.  * Constants
  111.  */
  112. #define    MAX_BSIZE        65536    /* 2^16 */
  113. #define MIN_BUFFERS        6
  114. #define MINHDRSIZE        512
  115. #define DEF_BUFSIZE        65536    /* 64 K */
  116. #define DEF_BUCKET_SIZE    256
  117. #define DEF_BUCKET_SHIFT    8    /* log2(BUCKET) */
  118. #define DEF_SEGSIZE        256
  119. #define DEF_SEGSIZE_SHIFT        8      /* log2(SEGSIZE)     */
  120. #define DEF_DIRSIZE        256
  121. #define DEF_FFACTOR        5
  122. #define SPLTMAX        8
  123. #define CHARKEY        "%$sniglet^&"
  124. #define NUMKEY            1038583
  125. #define VERSION_NO        3
  126. #define BYTE_SHIFT        3
  127. #define INT_TO_BYTE        2
  128. #define INT_BYTE_SHIFT        5
  129. #define ALL_SET        ((unsigned)0xFFFFFFFF)
  130. #define ALL_CLEAR        0
  131.  
  132.  
  133. #define PTROF(X)    ((BUFHEAD *)((unsigned)(X)&~0x3))
  134. #define ISMOD(X)    ((unsigned)(X)&0x1)
  135. #define DOMOD(X)    (X = (char *)( (unsigned)X | 0x1))
  136. #define ISDISK(X)    ((unsigned)(X)&0x2)
  137. #define DODISK(X)    (X = (char *)( (unsigned)X | 0x2))
  138.  
  139. #define BITS_PER_MAP    32
  140.  
  141. /* Given the address of the beginning of a big map, clear/set the nth bit */
  142.  
  143. #define CLRBIT(A,N) ((A)[N/BITS_PER_MAP] &= ~(1<<(N%BITS_PER_MAP)))
  144. #define SETBIT(A,N) ((A)[N/BITS_PER_MAP] |= (1<<(N%BITS_PER_MAP)))
  145. #define ISSET(A,N) ((A)[N/BITS_PER_MAP] & (1<<(N%BITS_PER_MAP)))
  146.  
  147. /* Overflow management */
  148. /*
  149.     Overflow page numbers are allocated per split point.
  150.     At each doubling of the table, we can allocate extra
  151.     pages.  So, an overflow page number has the top 5 bits
  152.     indicate which split point and the lower 11 bits indicate
  153.     which page at that split point is indicated (pages within
  154.     split points are numberered starting with 1).
  155.  
  156.  
  157. */
  158.  
  159. #define SPLITSHIFT    11
  160. #define SPLITMASK    0x7FF
  161. #define SPLITNUM(N)    (((unsigned)N) >> SPLITSHIFT)
  162. #define OPAGENUM(N)    (N & SPLITMASK)
  163. #define    OADDR_OF(S,O)    ((unsigned)((unsigned)S << SPLITSHIFT) + O)
  164.  
  165. #define BUCKET_TO_PAGE(B) \
  166.     B + hashp->HDRPAGES + (B ? hashp->SPARES[__log2(B+1)-1] : 0)
  167. #define OADDR_TO_PAGE(B)     \
  168.     BUCKET_TO_PAGE ( (1 << SPLITNUM(B)) -1 ) + OPAGENUM(B);
  169.  
  170. /*
  171.     page.h contains a detailed description of the page format.
  172.  
  173.     Normally, keys and data are accessed from offset tables in the
  174.     top of each page which point to the beginning of the key and
  175.     data.  There are four flag values which may be stored in these
  176.     offset tables which indicate the following:
  177.  
  178.     OVFLPAGE    Rather than a key data pair, this pair contains
  179.             the address of an overflow page.  The format of
  180.             the pair is:
  181.                 OVERFLOW_PAGE_NUMBER OVFLPAGE
  182.  
  183.     PARTIAL_KEY    This must be the first key/data pair on a page 
  184.             and implies that page contains only a partial key.  
  185.             That is, the key is too big to fit on a single page 
  186.             so it starts on this page and continues on the next.
  187.             The format of the page is:
  188.                 KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  189.                 
  190.                 KEY_OFF -- offset of the beginning of the key
  191.                 PARTIAL_KEY -- 1
  192.                 OVFL_PAGENO - page number of the next overflow page
  193.                 OVFLPAGE -- 0
  194.     FULL_KEY    This must be the first key/data pair on the page.  It
  195.             is used in two cases.  
  196.  
  197.             Case 1:
  198.                 There is a complete key on the page but no data
  199.                 (because it wouldn't fit).  The next page contains
  200.                 the data.
  201.  
  202.                 Page format it:
  203.                 KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  204.  
  205.                 KEY_OFF -- offset of the beginning of the key
  206.                 FULL_KEY -- 2
  207.                 OVFL_PAGENO - page number of the next overflow page
  208.                 OVFLPAGE -- 0
  209.  
  210.             Case 2:
  211.                 This page contains no key, but part of a large 
  212.                 data field, which is continued on the next page.
  213.  
  214.                 Page format it:
  215.                 DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  216.  
  217.                 KEY_OFF -- offset of the beginning of the data on
  218.                     this page
  219.                 FULL_KEY -- 2
  220.                 OVFL_PAGENO - page number of the next overflow page
  221.                 OVFLPAGE -- 0
  222.  
  223.     FULL_KEY_DATA    This must be the first key/data pair on the page.
  224.             There are two cases:
  225.  
  226.             Case 1:
  227.                 This page contains a key and the beginning of the
  228.                 data field, but the data field is continued on the
  229.                 next page.
  230.  
  231.                 Page format is:
  232.                 KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  233.  
  234.                 KEY_OFF -- offset of the beginning of the key
  235.                 FULL_KEY_DATA -- 3
  236.                 OVFL_PAGENO - page number of the next overflow page
  237.                 DATA_OFF -- offset of the beginning of the data 
  238.  
  239.             Case 2:
  240.                 This page contains the last page of a big data pair.
  241.                 There is no key, only the  tail end of the data 
  242.                 on this page.
  243.  
  244.                 Page format is:
  245.                 DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  246.  
  247.                 DATA_OFF -- offset of the beginning of the data on
  248.                     this page
  249.                 FULL_KEY_DATA -- 3
  250.                 OVFL_PAGENO - page number of the next overflow page
  251.                 OVFLPAGE -- 0
  252.  
  253.                 OVFL_PAGENO and OVFLPAGE are optional (they are
  254.                 not present if there is no next page).
  255. */
  256.  
  257. #define OVFLPAGE    0
  258. #define PARTIAL_KEY    1
  259. #define FULL_KEY    2
  260. #define FULL_KEY_DATA    3
  261. #define    REAL_KEY    4
  262. /* Short hands for accessing structure */
  263. #define BSIZE    hdr.bsize
  264. #define BSHIFT    hdr.bshift
  265. #define DSIZE    hdr.dsize
  266. #define SGSIZE    hdr.ssize
  267. #define SSHIFT    hdr.sshift
  268. #define LORDER    hdr.lorder
  269. #define MAX_BUCKET    hdr.max_bucket
  270. #define FFACTOR        hdr.ffactor
  271. #define HIGH_MASK    hdr.high_mask
  272. #define LOW_MASK    hdr.low_mask
  273. #define NKEYS        hdr.nkeys
  274. #define HDRPAGES    hdr.hdrpages
  275. #define SPARES        hdr.spares
  276. #define BITMAPS        hdr.bitmaps
  277. #define VERSION        hdr.version
  278. #define MAGIC        hdr.magic
  279. #define NEXT_FREE    hdr.next_free
  280. #define H_CHARKEY    hdr.h_charkey
  281.